// 
// File:   ast_iterator.h
// Author: cionescu
//
// Created on January 18, 2007, 6:25 PM
//

#ifndef _ast_iterator_H
#define	_ast_iterator_H

using namespace std;
#include <stack>
#include <boost/iterator/iterator_facade.hpp>

///////////////////////////////////////////////////////////////////////////////
//
//  A parse_tree_iterator allows to parse a previously generated parse tree as
//  if it would be a normal input stream.
//
//  This is an alternative to the semantic tree from prism_ast.h automatically
//  constructed by ast_parse. This is not used presently, just legacy code.
//  
///////////////////////////////////////////////////////////////////////////////
template <typename ParseTreeMatchT, typename ValueT>
class parse_tree_iterator: public boost::iterator_facade<parse_tree_iterator<ParseTreeMatchT, ValueT>, ValueT, boost::forward_traversal_tag>
{
public:
    typedef ParseTreeMatchT tree_match_t;

    typedef typename tree_match_t::container_t tree_t;
    typedef typename tree_match_t::parse_node_t parse_node_t;
    typedef typename tree_match_t::tree_iterator tree_iterator_t;
    typedef typename tree_match_t::const_tree_iterator
        const_tree_iterator_t;

    typedef typename parse_node_t::const_iterator_t const_iterator_t;
    /*typedef boost::detail::iterator_traits<const_iterator_t> iterator_traits;

    typedef typename iterator_traits::value_type value_type;
    typedef typename iterator_traits::pointer pointer;
    typedef typename iterator_traits::reference reference;
    typedef typename iterator_traits::difference_type difference_type;
    typedef std::forward_iterator_tag iterator_category;*/

private:
///////////////////////////////////////////////////////////////////////////////
//
//  The class node_stack contains the way back up the hierarchy from the
//  current parse node to the root parse node (needed, because the parsetree
//  itself doesn't contain uplinks).
//  This stack contains (node *, iterator) pairs.
//
///////////////////////////////////////////////////////////////////////////////
    class node_stack :
        public std::stack<std::pair<tree_t const *, const_tree_iterator_t> >
    {
        typedef std::stack<std::pair<tree_t const *, const_tree_iterator_t> > base_t;
        typedef std::pair<tree_t const *, const_tree_iterator_t> element_t;

    public:
        void push_top (tree_t const &target, const_tree_iterator_t iter){
            push(element_t(&target, iter));
        }
        
        void adjust_forward(){
            if (this->empty())
                go_up();
            else 
                (this->top()).second++;
        }
        
        void go_up(){       // goes up, 'till the next parse_node is found
            const_tree_iterator_t it = (this->top()).second;
            tree_t const* t = (this->top()).first;
            while(it == t->end()) {
                this->pop();
                it = (this->top()).second;
                t = (this->top()).first;
            }
            it++;
        }
        
        void go_down(){     // goes down, 'till a leaf node is found
            const_tree_iterator_t it = (this->top()).second;
            while (it->value.is_root()) {
                tree_t const* t = &(it->children);
                it = t->begin();
                this->push(element_t(t, it));
            }
        }

    // returns a reference to the current iterator of the current parse_node
        const_tree_iterator_t &act_iter() {
            return (this->top()).second;
        }

    // returns the current and end iterators of the current parse node
        const_tree_iterator_t act_const_iter() const {
            return (this->top()).second;
        }
        
        const_tree_iterator_t node_end() const{
            return (this->top()).first->end(); // ???
        }
    };

public:
    parse_tree_iterator(){}
    
    parse_tree_iterator(tree_t const &target_, const_tree_iterator_t iter_){
        nodes.push_top(target_,iter_); 
        nodes.go_down();
    }

private:
    friend class boost::iterator_core_access;
    
    void increment() {
        nodes.adjust_forward();
    }

    bool equal(parse_tree_iterator const& other) const {
        return true;
    }

    const_tree_iterator_t& dereference() const { 
        return nodes.act_iter(); 
    }

    node_stack nodes;
};



#endif	/* _ast_iterator_H */

